package com.yangli.leecode.mashib;

/**
 * @Description 位运算实现加减乘除
 * @Author liyang
 * @Date 2022/12/13 14:00
 */
public class BitOperation {
    public static void main(String[] args){
        System.out.println(add(20, 8));
        System.out.println(minus(20, 8));
        System.out.println(multi(20, 8));
        System.out.println(divide(21111110, 8));
    }

    public static int add(int a, int b){
        int c = a ^ b; // 没有进位的求和
        int d = (a & b) << 1; //求和的进位
        if ((c & d) != 0) { //表示有进位
            return add(c, d);
        }
        return c ^ d;
    }

    //x的相反数等于 ~x+1 a+ -b
    public static int minus(int a, int b){
        return add(a, add(~b, 1));
    }

    // b 的二进制值从右往左开始，如果 b 的某一位是 1 ，则把 a 左移一位的值加到结果中，模拟 1 * a，如果 b 的某一位是0，则 a 左移一位的值不加入结果中。 最后累加的结果就是a * b的答案。
    public static int multi(int a, int b){
        int res = 0;
        while (b != 0) {
            if ((b & 1) == 1) {//最后一位是不是为1
                res = add(res, a); //当前位置相加
            }
            a = a << 1;//3*7 = 3*1 + 3*2+ 3*4
            b = b >> 1;
        }
        return res;
    }

    //a = b * (2^7) + b * (2^4) + b * (2^1)，则 c 的二进制一定是10010010。 所以，我们的思路可以转换成 a 是由几个 (b * 2的某次方)的结果组成，
    public static int divide(int a, int b){
        //实现除法的时候，为了防止溢出，我们首先把所有数先转换成正数来算
        int x = isNeg(a) ? add(~a, 1) : a;
        int y = isNeg(b) ? add(~b, 1) : b;
        int res = 0;
        for (int i = 31; i > -1; i--) {
            if ((a >> i) >= b) {
                res |= 1 << i;//比加法速度更快，如果没有进位冲突用 |=
                a = minus(a, b << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? add(~res, 1) : res;//负负等正==>亦或
    }

    public static boolean isNeg(int n){
        return n < 0;
    }


    public static int divide2(int a, int b){
        int res = 0;
        for (int i = 31; i > -1; i--) {
            if ((a >> i) >= b) {
                res |= 1 << i;
                a = minus(a, b << i);
            }
        }
        return res;
    }

}
